package com.guchenbo.example.dfs;

import java.util.*;

/**
 * @author guchenbo
 * @date 2024/7/17
 */
public class ParseView {
    private static Map<String, View> dbs = new LinkedHashMap<>();
    private static Map<String, View> dbs2 = new LinkedHashMap<>();

    public static void main(String[] args) {
        /*
                    v1
                  /    \
               v2        v3
              / \       /  \
            v4 v5     v6   v7
                        /  \ \
                       v10  \  \
                       /  \  \   \
                       v11   v8 v9
         */
        View root = buildView();
        postorder1(root);
        System.out.println("sequence");
        dbs.keySet().forEach(System.out::println);

        postorder2(root);
        System.out.println("sequence");
        dbs2.keySet().forEach(System.out::println);
    }

    private static void postorder2(View root) {
        Set<String> visited = new HashSet<>();
        Stack<View> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            View view = stack.peek();
            List<View> from = view.getFrom();
            if (from == null || from.isEmpty() || visited.contains(view.getName())) {
                stack.pop();
                dbs2.put(view.getName(), view);
                continue;
            }
            for (int i = from.size() - 1; i >= 0; i--) {
                stack.push(from.get(i));
            }
            visited.add(view.getName());
        }
    }

    private static void postorder1(View root) {
        Stack<View> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            View view = stack.peek();
            List<View> from = view.getFrom();
            if (from != null) {
                boolean allExist = true;
                for (View v : from) {
                    if (!dbs.containsKey(v.getName())) {
                        stack.push(v);
                        allExist = false;
                    }
                }
                if (allExist) {
                    dbs.put(view.getName(), view);
                    stack.pop();
                }
            } else {
                dbs.put(view.getName(), view);
                stack.pop();
            }
        }
    }

    private static View buildView() {
        View v1 = view("v1");
        View v2 = view("v2");
        View v3 = view("v3");
        v1.setFrom(Arrays.asList(v2, v3));

        View v4 = view("v4");
        View v5 = view("v5");
        v2.setFrom(Arrays.asList(v4, v5));
        View v6 = view("v6");
        View v7 = view("v7");
        v3.setFrom(Arrays.asList(v6, v7));
        View v8 = view("v8");
        View v9 = view("v9");
        View v10 = view("v10");
        v7.setFrom(Arrays.asList(v8, v9, v10));
        View v11 = view("v11");
        v10.setFrom(Arrays.asList(v8, v9, v11));
        return v1;
    }

    private static View view(String name) {
        return View.builder().name(name).build();
    }
}
